package com.dyw.Day16;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Devil
 * @create 2022-01-25-23:23
 *
 * 给定一个二叉树，找出其最大深度。
 *
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 *
 *
 * 思路: 在层序遍历二叉树的过程中 借助deque(队列)来遍历 deque记录每层的结点 只要size>0就算有记录也就算一层
 */
@SuppressWarnings("all")
public class Demo02 {
    public int maxDepth(TreeNode root) {
        //创建一个队列
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        //计数器用于记录二叉树的层数
        int count=0;
        if(root==null){
            return count;
        }

        while(!deque.isEmpty()){
            //获取每一层的个数
            int size = deque.size();
            while(size-->0){
                TreeNode cur = deque.pop();
                if(cur.left!=null){
                    deque.add(cur.left);
                }
                if(cur.right!=null){
                    deque.add(cur.right);
                }
            }
            //扫过一层 记录个数(只要一层中有结点就算一层)
            count++;
        }

        return count;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}